425D - Sereja and Squares - CodeForces Solution

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>
  
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = 0;
const ld eps = 1e-12;
const double pi = atan2(0, -1);
const int ABC = 26;

const int B = 333;

int c_xs[N + 1], c_ys[N + 1];
vector<int> ys[N + 1];
unordered_set<int> xs[N + 1];

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    int n;
    cin >> n;
    rep(i, 0, n) {
        int x, y;
        cin >> x >> y;
        c_ys[x]++; ys[x].push_back(y);
        c_xs[y]++; xs[y].insert(x);
    }
    int ans = 0;
    vector<int> big_x;
    rep(x, 0, N + 1) {
        sort(ys[x].begin(), ys[x].end());
        if (c_ys[x] <= B) {
            for (int i = 0; i < c_ys[x]; i++) {
                for (int j = i + 1; j < c_ys[x]; j++) {
                    int y1 = ys[x][i], y2 = ys[x][j];
                    int d = y2 - y1;
                    if (x - d >= 0 && c_ys[x - d] > B && xs[y1].find(x - d) != xs[y1].end() && xs[y2].find(x - d) != xs[y2].end()) {
                        ans++;
                    }
                    if (xs[y1].find(x + d) != xs[y1].end() && xs[y2].find(x + d) != xs[y2].end()) {
                        ans++;
                    }
                }
            }
        } else {
            big_x.push_back(x);
        }
    }
    rep(i, 0, sz(big_x)) {
        rep(j, i + 1, sz(big_x)) {
            int x1 = big_x[i], x2 = big_x[j];
            int d = x2 - x1;
            int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
            while (l1 < c_ys[x1] && l2 < c_ys[x2]) {
                if (ys[x1][l1] == ys[x2][l2]) {
                    while (r1 < c_ys[x1] && ys[x1][r1] < ys[x1][l1] + d) {
                        r1++;
                    }
                    while (r2 < c_ys[x2] && ys[x2][r2] < ys[x2][l2] + d) {
                        r2++;
                    }
                    if (r1 < c_ys[x1] && ys[x1][r1] == ys[x1][l1] + d && r2 < c_ys[x2] && ys[x2][r2] == ys[x2][l2] + d) {
                        ans++;
                    }
                }
                if (ys[x1][l1] < ys[x2][l2]) {
                    l1++;
                } else {
                    l2++;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}